package org.example.myleet.mathematics;

import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.ListNode;
import org.example.myleet.Utils.MathUtil;
import org.example.myleet.Utils.TreeNode;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class MathematicsSolution {

    //面试题 05.02
    public String printBin(double num) {
        int i = 0;
        StringBuilder answer = new StringBuilder();
        answer.append("0.");
        while (num != 0 && i < 32) {
            double num2 = num * 2;
            if (num2 >= 1.0) {
                answer.append('1');
            } else {
                answer.append('0');
            }
            num = num2 >= 1.0 ? (num2 - 1.0) : num2;
            ++i;
        }
        if (i >= 32) {
            return "ERROR";
        }
        return answer.toString();
    }

    //p29
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            throw new RuntimeException("除以0，无意义");
        }
        if (dividend == 0) {
            return 0;
        }
        if (dividend == divisor) {
            return 1;
        }
        if (divisor == 1) {
            //除数是1
            return dividend;
        }
        if (divisor == -1) {
            //除数是-1
            if (dividend == Integer.MIN_VALUE) {
                //溢出，返回MAX
                return Integer.MAX_VALUE;
            }
            //返回被除数的负数
            return -dividend;
        }
        //结果是否负数，true-有负号，负数
        boolean sign = false;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            sign = true;
        }
        //对除数和被除数取绝对值
        long dividendP = Math.abs(dividend);
        dividendP = Math.abs(dividendP);
        long divisorP = Math.abs(divisor);
        divisorP = Math.abs(divisorP);
        if (dividendP < divisorP) {
            //除数大于被除数，结果为0
            return 0;
        }
        //计算除数和被除数的位数之差
        int dividendBitCount = 0;
        long dividendCopy = dividendP;
        while (dividendCopy > 0) {
            dividendCopy >>= 1;
            ++dividendBitCount;
        }
        int divisorBitCount = 0;
        long divisorCopy = divisorP;
        while (divisorCopy > 0) {
            divisorCopy >>= 1;
            ++divisorBitCount;
        }
        int bitDiff = dividendBitCount - divisorBitCount;
        //初始化商和余数
        long quotient = 0;
        long remainder = dividendP;
        //实测发现如果除数和被除数都是2的幂，需要给余数+1防止除数移位后和被除数完全一样
        boolean powOf2 = isPowOf2(remainder) && isPowOf2(divisorP);
        if (powOf2) {
            ++remainder;
        }
        //核心功能，利用位运算做除法
        for (int i = bitDiff; i >= 0; --i) {
            //计算被除数在当前位置的放大结果
            long curDivisor = divisorP << i;
            if (remainder > 0) {
                if (remainder >= curDivisor) {
                    //余数可做减法，进行相减，且对应的位置由1占领
                    remainder -= curDivisor;
                    quotient <<= 1;
                    quotient += 1;
                } else {
                    //否则对应位置由0占领
                    quotient <<= 1;
                }
            }
        }
        if (powOf2 && remainder > 0) {
            //去掉被加上的1
            --remainder;
        }
        //最后考虑符号位
        if (sign) {
            return (int) -quotient;
        }
        if (quotient > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int) quotient;
    }
    private boolean isPowOf2(long num) {
        if (num == 1L) {
            return false;
        }
        return (num & (num - 1)) == 0;
    }

    //p31
    /**
     * https://blog.csdn.net/qq_34672688/article/details/79557380
     * 字典顺序排序
     * 获取下一个字典顺序的方法：
     * 1、从右往左找，找到第一个位置k，令i=k-1（左邻位置），且num[i]<num[k]，左邻小于右邻
     * 2、从右至左找到第一个比i位置大的数，位置j
     * 3、交换i、j位置的数值
     * 4、从i+1位置开始，右边的数值全部按升序排列
     */
    public void nextPermutation(int[] nums) {
        for (int k=nums.length-1; k>0; k--) {
            int i=k-1;
            if (nums[i]<nums[k]) {
                for (int j=nums.length-1; j>i; j--) {
                    if (nums[i]<nums[j]) {
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        Arrays.sort(nums, k, nums.length);
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
    }

    //剑指Offer 38
    public String[] permutation(String s) {
        Set<String> result = new HashSet<>();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String nextLexicographic = new String(chars);
        while (null != nextLexicographic) {
            result.add(nextLexicographic);
            nextLexicographic = generateNextLexicographic(nextLexicographic);
        }
        return result.toArray(new String[0]);
    }
    /**
     * 生成下一个字典序的字符串，如果已经是最大字典序，则返回null
     */
    private String generateNextLexicographic(String s) {
        char[] chars = s.toCharArray();
        //1、
        int pj = findPj(chars);
        if (pj < 0) {
            //从头至尾单调递减，已经是最大的字典序，找不到下一个字典序
            return null;
        }
        //2、
        int pk = findPk(chars, pj);
        if (pk < 0) {
            return null;
        }
        //3、
        swap(chars, pj, pk);
        //4、
        reverse(chars, pj + 1, chars.length - 1);
        return new String(chars);
    }
    private int findPj(char[] chars) {
        char c = chars[chars.length - 1];
        for (int i = chars.length - 2; i > -1; --i) {
            if (chars[i] < c) {
                return i;
            }
            c = chars[i];
        }
        return -1;
    }
    private int findPk(char[] chars, int pj) {
        char c = chars[pj];
        for (int i = pj + 1; i < chars.length; ++i) {
            if (chars[i - 1] > c && chars[i] <= c) {
                return i - 1;
            }
        }
        return chars.length - 1;
    }
    private void swap(char[] chars, int pj, int pk) {
        char c = chars[pj];
        chars[pj] = chars[pk];
        chars[pk] = c;
    }
    private void reverse(char[] chars, int from, int to) {
        while (from < to) {
            swap(chars, from, to);
            ++from;
            --to;
        }
    }

    //剑指Offer 62
    /**
     * 倒推解，舒服
     * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
     */
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }

    //p43. 字符串相乘。模拟小学乘法计算
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        StringBuilder main = new StringBuilder(num1);
        main.reverse();
        StringBuilder sub = new StringBuilder(num2);
        sub.reverse();
        StringBuilder sum = new StringBuilder("0");
        StringBuilder product;
        for (int i = 0; i < sub.length(); ++i) {
            //multiply single
            int singleNumber = sub.charAt(i) - '0';
            product = new StringBuilder();
            for (int j = 0; j < i; ++j) {
                product.append('0');
            }
            int shift = 0;
            for (int j = 0; j < main.length(); ++j) {
                int mj = main.charAt(j) - '0';
                int prod = mj * singleNumber + shift;
                int remainder = prod % 10;
                shift = prod / 10;
                product.append(remainder);
            }
            if (shift > 0) {
                product.append(shift);
            }
            //add two numbers in String type
            StringBuilder sb1 = sum;
            StringBuilder sb2 = product;
            StringBuilder sb = new StringBuilder();
            shift = 0;
            int j;
            for (j = 0; j < sb1.length(); ++j) {
                int sb1j = sb1.charAt(j) - '0';
                int sb2j = j >= sb2.length() ? 0 : sb2.charAt(j) - '0';
                int s = sb1j + sb2j + shift;
                int remainder = s % 10;
                shift = s / 10;
                sb.append(remainder);
            }
            for (; j < sb2.length(); ++j) {
                int sb2j = sb2.charAt(j) - '0';
                int s = sb2j + shift;
                int remainder = s % 10;
                shift = s / 10;
                sb.append(remainder);
            }
            if (shift > 0) {
                sb.append(shift);
            }
            sum = sb;
        }
        return sum.reverse().toString();
    }

    /**
     * p48. 旋转图像
     * 翻转操作代替旋转操作
     * 先对角线镜像翻转后再左右翻转，实现顺时针90度旋转矩阵
     */
    public void rotate(int[][] matrix) {
        for (int i=0;i<matrix.length;i++) {
            for (int j=i;j<matrix[i].length;j++) {
                if (i==j) {
                    continue;
                }
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
        for (int i=0;i<matrix.length;i++) {
            for (int j = 0; j < matrix[i].length/2; j++) {
                int t = matrix[i][j];
                int idx = matrix[i].length-1-j;
                matrix[i][j] = matrix[i][idx];
                matrix[i][idx] = t;
            }
        }
    }

    /**
     * 66【模拟】加一
     * 思路：模拟，小学加法
     */
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        ++digits[n - 1];
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] > 9) {
                int shift = digits[i] / 9;
                digits[i] -= shift * 10;
                if (i > 0) {
                    digits[i - 1] += shift;
                } else {
                    int[] newDigits = new int[n + 1];
                    System.arraycopy(digits, 0, newDigits, 1, n);
                    newDigits[0] = shift;
                    digits = newDigits;
                }
            }
        }
        return digits;
    }

    /**
     * 89【数学公式】格雷编码
     */
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < 1 << n; i++) {
            ret.add((i >> 1) ^ i);
        }
        return ret;
    }

    /**
     * 135【数学方法】分发糖果
     * O(n)
     * 2 ms
     */
    public int candy(int[] ratings) {
        if (ratings.length == 0) {
            return 0;
        }
        int minIdx = 0, minRating = ratings[0];
        //先找出打分最小的孩子，作为起始点
        for (int i = 1; i < ratings.length; i++) {
            if (minRating > ratings[i]) {
                minRating = ratings[i];
                minIdx = i;
            }
        }
        //缓存每个孩子应得的最小糖果数，默认0，最后算总和的时候每个孩子多给一个就满足题意最少得1颗
        int[] candies = new int[ratings.length];
        //接下来按照评分最低的孩子作为分割点，分成两边进行计算，评分最低的孩子毋庸置疑肯定是给0（最少糖果）
        for (int i = minIdx - 1; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                //相邻孩子评分更高，获得更多糖果
                candies[i] = candies[i + 1] + 1;
            } else if (ratings[i] < ratings[i + 1]) {
                //向前延伸时，出现当前孩子评分比上一个孩子评分低，此时需要纠正前面的糖果分配
                int j = i;
                while (j < minIdx) {
                    if (ratings[j] < ratings[j + 1] && candies[j] >= candies[j + 1]) {
                        //当前孩子评分比上一个孩子评分低，且评分高的孩子糖果没有比当前孩子多，需要分配更多糖果
                        candies[j + 1] = candies[j] + 1;
                    } else {
                        //这一步比较关键，没有这一步跳出会导致运算时间达到300+ms
                        //当不存在违反规则的情况时，其实前面的数据已经捋顺了，无需再倒回去检查，可以提前结束回溯纠正
                        break;
                    }
                    ++j;
                }
            } else {
                //当前孩子评分和上一个孩子评分持平，可以给最少的糖果数量
                candies[i] = 0;
            }
        }
        //另一个方向，原理和上面的一样，但是逻辑相反。如果直接把两种方向合成一种，并且从头开始计算，虽然结果也是对的，但是运算时间从2ms变成500+ms
        //其原因应该是因为每次纠正都要经过那个评分最低的孩子，导致回溯纠正的情况大量增加
        for (int i = minIdx + 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            } else if (ratings[i] < ratings[i - 1]) {
                int j = i;
                while (j > minIdx) {
                    if (ratings[j] < ratings[j - 1] && candies[j] >= candies[j - 1]) {
                        candies[j - 1] = candies[j] + 1;
                    } else {
                        break;
                    }
                    --j;
                }
            } else {
                candies[i] = 0;
            }
        }
        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        //每个孩子多给1个，满足题意最少得1颗
        sum += ratings.length;
        return sum;
    }

    /**
     * 136【位运算】只出现一次的数字
     */
    public int singleNumber(int[] nums) {
        int n = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            //异或运算后，如果重复出现了某个数字，该数字会被去掉（例如3^3=0）
            n = n ^ nums[i];
        }
        return n;
    }


    /**
     * 149【哈希+数学】直线上最多的点数
     * 使用y = a * x + b联立的方式求斜率a以及截距b方法
     * 结合哈希表快速归类共线点，双循环进行点线遍历
     * 注意事项：
     * 1、x=n的情况，此时没有斜率，不能求出a，因此使用特殊的x=n作为哈希的key
     * 2、点与点要实现equals方法进行去重
     * 3、注意精度，题目要求点的坐标值不超过10^4，因此相除后为了区分斜率a，需要足够大的精度
     */
    static class Point149 {
        private BigDecimal x;
        private BigDecimal y;
        public Point149(BigDecimal x, BigDecimal y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point149 point149 = (Point149) o;
            return (x.compareTo(point149.x) == 0) &&
                    (y.compareTo(point149.y) == 0);
        }
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
    public int maxPoints(int[][] points) {
        Point149[] point149Arr = new Point149[points.length];
        for (int i = 0; i < points.length; ++i) {
            point149Arr[i] = new Point149(BigDecimal.valueOf(points[i][0]), BigDecimal.valueOf(points[i][1]));
        }
        Map<String, Set<Point149>> linePointMap = new HashMap<>();
        for (int i = 0; i < point149Arr.length; ++i) {
            for (int j = i + 1; j < point149Arr.length; ++j) {
                String lineSig;
                BigDecimal deltaX = point149Arr[i].x.subtract(point149Arr[j].x);
                BigDecimal deltaY = point149Arr[i].y.subtract(point149Arr[j].y);
                if (deltaX.compareTo(BigDecimal.ZERO) == 0) {
                    //无斜率情况
                    lineSig = "x=" + point149Arr[i].x.setScale(9, BigDecimal.ROUND_HALF_UP).toPlainString();
                } else {
                    //求斜率
                    BigDecimal a = deltaY.setScale(9, RoundingMode.HALF_UP).divide(deltaX, RoundingMode.HALF_UP);
                    //求截距
                    BigDecimal b = point149Arr[i].y.subtract(point149Arr[i].x.multiply(a)).setScale(9, RoundingMode.HALF_UP);
                    lineSig = a.toPlainString() + "," + b.toPlainString();
                }
                Set<Point149> linePointSet149 = linePointMap.getOrDefault(lineSig, new HashSet<>());
                linePointSet149.add(point149Arr[i]);
                linePointSet149.add(point149Arr[j]);
                linePointMap.put(lineSig, linePointSet149);
            }
        }
        int mostPoints = 1;
        for (Map.Entry<String, Set<Point149>> entry : linePointMap.entrySet()) {
            mostPoints = Math.max(mostPoints, entry.getValue().size());
        }
        return mostPoints;
    }

    /**
     * 166【模拟、哈希表】分数到小数
     * 思路：模拟小学除法运算
     */
    public String fractionToDecimal(int numerator, int denominator) {
        //先转换到long，防止溢出
        long n = numerator, d = denominator;
        //求出结果是否负数
        boolean negative = n * d < 0;
        //将负号先全部去掉，对整数做除法
        n = Math.abs(n);
        d = Math.abs(d);
        //整数部分
        long integer = 0;
        if (n >= d) {
            integer = n / d;
        }
        long remainder = n % d;
        if (remainder == 0) {
            //能整除，那就没有小数部分了
            if (negative) {
                return "-" + integer + "";
            }
            return integer + "";
        }
        //小数部分
        StringBuilder sb1 = new StringBuilder();
        sb1.append(integer).append('.');
        //用哈希表记录余数是否出现，以及余数出现时对应的小数部分的长度
        Map<Long, Integer> remainderPositionMap = new HashMap<>();
        StringBuilder sb2 = new StringBuilder();
        for (;;) {
            if (remainderPositionMap.containsKey(remainder)) {
                //余数再次出现，说明小数开始循环，结束循环，并标记循环部分
                int position = remainderPositionMap.get(remainder);
                sb2.insert(position, '(').append(')');
                break;
            }
            //记忆化余数出现时小数部分的长度
            remainderPositionMap.put(remainder, sb2.length());
            //余数不够大，乘以10试试
            remainder *= 10;
            if (remainder < d) {
                //余数仍然不够大，则此结果位叠加0，提前进入下一循环
                sb2.append(0);
                continue;
            }
            //余数足够大了，可以继续做除法，先求除法结果，并叠加到小数部分
            long t1 = remainder / d;
            sb2.append(t1);
            //求出新的余数
            long newRemainder = remainder % d;
            if (newRemainder == 0) {
                //可以整除，说明小数部分有限，结束
                break;
            }
            remainder = newRemainder;
        }
        //整数部分连接小数部分得到结果
        if (negative) {
            //结果为负数的情况要添加负号
            return sb1.insert(0, '-').append(sb2).toString();
        }
        return sb1.append(sb2).toString();
    }

    /**
     * 168【进制转换】Excel表列名称
     * 10进制转26进制，比较特殊的是没有0
     */
    private static final String LEXICOGRAPHIC = "ZABCDEFGHIJKLMNOPQRSTUVWXYZ";
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        int divided = columnNumber;
        while (divided > 26) {
            int remainder = divided % 26;
            sb.append(LEXICOGRAPHIC.charAt(remainder));
            if (remainder == 0) {
                //由于没有0，因此对于当低一位的remainder为0时，高一位需要借一位（-1）
                --divided;
            }
            divided /= 26;
        }
        sb.append(LEXICOGRAPHIC.charAt(divided));
        return sb.reverse().toString();
    }

    /**
     * 171【禁止转换】Excel 表列序号
     * 从26进制转换为10进制
     */
    public int titleToNumber(String columnTitle) {
        int sum = 0;
        for (int i = 0; i < columnTitle.length(); ++i) {
            char c = columnTitle.charAt(i);
            sum = sum * 26 + (c - 'A' + 1);
        }
        return sum;
    }

    /**
     * 172【数学】阶乘后的零
     * n! 尾零的数量即为 n! 中因子 101010 的个数，而 10=2×5，因此转换成求 n! 中质因子 2 的个数和质因子 5 的个数的较小值。
     * 由于质因子 5 的个数不会大于质因子 2 的个数（例如1~6中2的质因子在2、4、6中都有，但是5的质因子只在5中有），我们可以仅考虑质因子 5 的个数。
     */
    public int trailingZeroes(int n) {
        Map<Integer, Integer> numberMap5Count = new HashMap<>(10000);
        int zeroCount = 0;
        for (int i = 1; i <= n; ++i) {
            int number = i;
            int zCount = 0;
            if (number % 5 == 0) {
                ++zCount;
                number = number / 5;
                if (number % 5 == 0) {
                    Integer fiveCount = numberMap5Count.get(number);
                    if (null != fiveCount) {
                        zCount += fiveCount;
                    }
                }
                numberMap5Count.put(i, zCount);
                zeroCount += zCount;
            }
        }
        return zeroCount;
    }

    /**
     * 190【位运算+分治思想】颠倒二进制位
     * 1 ms
     * 分治思想
     */
    public int reverseBits(int n) {
        System.out.println(toFixBinaryString(n));
        //第一次将左右对半交换
        n = ((n & 0b11111111111111110000000000000000) >>> 16) | ((n & 0b00000000000000001111111111111111) << 16);
        System.out.println(toFixBinaryString(n));
        //第二次将一半中的左右对半再交换
        n = ((n & 0b11111111000000001111111100000000) >>> 8) | ((n & 0b00000000111111110000000011111111) << 8);
        System.out.println(toFixBinaryString(n));
        n = ((n & 0b11110000111100001111000011110000) >>> 4) | ((n & 0b00001111000011110000111100001111) << 4);
        System.out.println(toFixBinaryString(n));
        n = ((n & 0b11001100110011001100110011001100) >>> 2) | ((n & 0b00110011001100110011001100110011) << 2);
        System.out.println(toFixBinaryString(n));
        //直到最后将相邻位置左右交换，完成顺序颠倒处理
        n = ((n & 0b10101010101010101010101010101010) >>> 1) | ((n & 0b01010101010101010101010101010101) << 1);
        System.out.println(toFixBinaryString(n));
        System.out.println("---------------------------");
//        n = (n >>> 16) | (n << 16);
//        System.out.println(toFixBinaryString(n));
//        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
//        System.out.println(toFixBinaryString(n));
//        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
//        System.out.println(toFixBinaryString(n));
//        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
//        System.out.println(toFixBinaryString(n));
//        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
//        System.out.println(toFixBinaryString(n));
//        System.out.println("---------------------------");
        return n;
    }

    /**
     * 204【厄拉多塞筛法】计数质数
     * 质数筛
     * 1.依次从2开始筛选2的倍数将小于n的数cover掉
     * 2.从未cover掉的数继续重复步骤1直到所有的数都被cover掉
     * https://www.cnblogs.com/lxrnn/p/12834570.html
     * https://images.cnblogs.com/cnblogs_com/lxrnn/1758111/o_200506014141dw.gif
     */
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        List<Integer> primes = new ArrayList<>();
        int[] numbers = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            numbers[i] = i;
        }
        for (int i = 2; i <= n; i++) {
            if (numbers[i] > 0) {
                primes.add(numbers[i]);
                for (int j = i, k = 1; j <= n; k++, j = k * i) {
                    //划调素数的倍数
                    numbers[j] = 0;
                }
            }
        }
        if (n == primes.get(primes.size() - 1)) {
            return primes.size() - 1;
        }
        return primes.size();
    }

    public List<Integer> findPrimes(int n) {
        if (n < 2) return Collections.emptyList();
        if (n < 3) return Collections.singletonList(2);
        List<Integer> primes = new ArrayList<>(n);
        int[] numbers = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            numbers[i] = i;
        }
        for (int i = 2; i <= n; i++) {
            if (numbers[i] > 0) {
                primes.add(numbers[i]);
                for (int j = i, k = 1; j <= n; k++, j = k * i) {
                    //划调素数的倍数
                    numbers[j] = 0;
                }
            }
        }
        return primes;
    }

    private String toFixBinaryString(int i) {
        //此方式是固定输出32位长度的二进制数字以展示交换过程
        StringBuilder sb = new StringBuilder(Integer.toBinaryString(i));
        while (sb.length() < 32) {
            sb.insert(0, '0');
        }
        return sb.toString();
    }

    /**
     * 223【几何数学】矩形面积
     */
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        //讨论两个矩形未减去交集时覆盖的面积
        int sa = (ax2 - ax1) * (ay2 - ay1);
        int sb = (bx2 - bx1) * (by2 - by1);
        //计算覆盖面积并减去
        int cover = 0;
        int coverH = 0;
        int coverW = 0;
        if (by1 < ay2) {
            if (by1 < ay1) {
                if (by2 > ay1) {
                    if (by2 < ay2) {
                        coverH = by2 - ay1;
                    } else {
                        coverH = ay2 - ay1;
                    }
                }
            } else {
                if (by2 > ay1) {
                    if (by2 < ay2) {
                        coverH = by2 - by1;
                    } else {
                        coverH = ay2 - by1;
                    }
                }
            }
        }
        if (bx1 < ax2) {
            if (bx1 < ax1) {
                if (bx2 > ax1) {
                    if (bx2 < ax2) {
                        coverW = bx2 - ax1;
                    } else {
                        coverW = ax2 - ax1;
                    }
                }
            } else {
                if (bx2 > ax1) {
                    if (bx2 < ax2) {
                        coverW = bx2 - bx1;
                    } else {
                        coverW = ax2 - bx1;
                    }
                }
            }
        }
        coverH = Math.max(coverH, 0);
        coverW = Math.max(coverW, 0);
        cover = coverH * coverW;
        return sa + sb - cover;
    }

    /**
     * 229【摩尔投票法】多数元素 II
     * 官方思路：摩尔投票法
     * 首先简单证明，由于统计频数超过n/3的众数，最终结果必然最多只有2个
     * 然后就是摩尔投票法的思路，即"相互抵消"，每当出现3个不同的数字时，对3个数字的当前出现频数进行-1的抵消
     * 然后最后只有3种结果：1）什么都没剩下，2）剩下1个数，3）剩下2个数
     * 然后对剩下的数重新进行频数检查，以确保答案准确
     */
    public List<Integer> majorityElement(int[] nums) {
        int leastCount = nums.length / 3 + 1;
        int[] candidates = new int[2];
        candidates[0] = Integer.MIN_VALUE;
        candidates[1] = Integer.MIN_VALUE;
        int[] counts = new int[2];
        for (int num : nums) {
            //尝试在候选的两个数中寻找当前数num
            if (num == candidates[0]) {
                ++counts[0];
                continue;
            }
            if (num == candidates[1]) {
                ++counts[1];
                continue;
            }
            if (candidates[0] == Integer.MIN_VALUE) {
                candidates[0] = num;
                ++counts[0];
                continue;
            }
            if (candidates[1] == Integer.MIN_VALUE) {
                candidates[1] = num;
                ++counts[1];
                continue;
            }
            //找不到，说明已经出现3个不同的数字，进行抵消
            --counts[0];
            --counts[1];
            //抵消之后，如果出现频数为0的情况，空出对应位置
            if (counts[0] == 0) {
                candidates[0] = Integer.MIN_VALUE;
            }
            if (counts[1] == 0) {
                candidates[1] = Integer.MIN_VALUE;
            }
        }
        //最后再做一次频数检查以得到准确结果
        List<Integer> result = new ArrayList<>();
        if (candidates[0] != Integer.MIN_VALUE || candidates[1] != Integer.MIN_VALUE) {
            counts[0] = 0;
            counts[1] = 0;
            for (int num : nums) {
                if (num == candidates[0]) {
                    ++counts[0];
                }
                if (num == candidates[1]) {
                    ++counts[1];
                }
            }
            if (counts[0] >= leastCount) {
                result.add(candidates[0]);
            }
            if (counts[1] >= leastCount) {
                result.add(candidates[1]);
            }
        }
        return result;
    }

    /**
     * 230【Morris中序遍历】二叉搜索树中第K小的元素
     */
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        morrisSearch(root, result, k);
        return result.get(k - 1);
    }
    /**
     * 思路，Morris中序遍历，对于cur节点，对其左子节点的右叶子节点进行回环连接到cur
     * 然后遍历其左子节点，左子节点遍历完再遍历右子节点
     * 当发现cur节点右叶子节点的右侧是cur时，说明cur节点的子树已经遍历完成，解除回环连接
     * 中序遍历时，在每个节点的遍历顺序中将节点值加入到数组中得到二叉搜索树的按顺序展开结果
     */
    private void morrisSearch(TreeNode root, List<Integer> result, int k) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode prev = cur.left;
                while (prev.right != null && prev.right != cur) {
                    //找到cur节点的左子节点的右叶子节点
                    prev = prev.right;
                }
                if (prev.right == null) {
                    //第一次遍历prev的右子节点，做回环连接
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    //第二次遍历prev的右子节点，解除回环连接，并作为真正遍历的时机
                    prev.right = null;
                    //中序遍历中访问中间节点或右子节点
                    result.add(cur.val);
                    if (result.size() == k) {
                        //不用这个提前结束可以得到完整的顺序展开结果
                        return;
                    }
                    cur = cur.right;
                }
            } else {
                //中序遍历中访问左节点或右子节点
                result.add(cur.val);
                if (result.size() == k) {
                    //不用这个提前结束可以得到完整的顺序展开结果
                    return;
                }
                cur = cur.right;
            }
        }
    }

    /**
     * 231【数学】2 的幂
     */
    public boolean isPowerOfTwo(int n) {
        if (n < 1) return false;
        //2的n次幂的二进制形式为1b10000000，2的n次幂-1的二进制形式为1b01111111
        //  10000000
        //& 01111111
        //----------
        //  00000000
        return (n & (n - 1)) == 0;
    }

    /**
     * 233【归纳总结+递归】数字 1 的个数
     * 归纳总结发现规律
     * F(n) = a * Level(a) + b + F(n的去掉最高位部分)
     * 其中，a是n的最高位，b分两种情况，如果a大于1，则是寻找对应的整百整千，例如10、100、1000...，否则是n - 对应的999，第三部分是递归
     */
    public int countDigitOne(int n) {
        return (int) calOne(n);
    }
    private static final long[] LEVELS = new long[]{1L,20L,300L,4000L,50000L,600000L,7000000L,80000000L,900000000L,10000000000L,110000000000L};
    private static final long[] MILESTONES = new long[]{9L,99L,999L,9999L,99999L,999999L,9999999L,99999999L,999999999L,9999999999L,99999999999L};
    private long calOne(long n) {
        if (n < 1) {
            return 0;
        }
        if (n <= 9) {
            return 1;
        }
        int i;
        for (i = 1; i < 11; ++i) {
            if (n == MILESTONES[i - 1]) {
                return LEVELS[i - 1];
            }
            if (MILESTONES[i - 1] < n && n < MILESTONES[i]) {
                break;
            }
        }
        long a = n / (MILESTONES[i - 1] + 1);
        long b;
        if (a > 1L) {
            b = MILESTONES[i - 1] + 1;
        } else {
            b = n - MILESTONES[i - 1];
        }
        long c = n % (MILESTONES[i - 1] + 1);
        return a * LEVELS[i - 1] + b + calOne(c);
    }

    /**
     * 240【类比二叉搜索树】搜索二维矩阵 II
     * 官方思路：从矩阵的右上角来看，是一棵二叉搜索树的根，左边（--col）是进入较小的子树，右边（++row）是进入较大的子树
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int row = 0, col = n - 1;
        while (row < m && col >= 0) {
            if (matrix[row][col] > target) {
                --col;
            } else if (matrix[row][col] < target) {
                ++row;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 263【数学】丑数
     * 1 ms
     * 2、3、5各试一试，能除尽就除，相当于给这个数剥离一个丑数因子
     * 注意！N/2比N>>1的计算要慢，用位运算更快
     */
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        int N = n;
        while (N > 2) {
            if (N % 2 == 0) {
                N = N >> 1;
            } else if (N % 3 == 0) {
                N = N / 3;
            } else if (N % 5 == 0) {
                N = N / 5;
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * 273【分治】整数转换英文表示
     * 英文表达方式是三位三位进行，所以每三位就取出来进行处理
     */
    public String numberToWords(int num) {
        if (num == 0) {
            //特殊情况
            return "Zero";
        }
        //20以内的基数词
        String[] CARDINAL_NUMBER = new String[]{"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        //20以上各个10的基数词
        String[] TENS_CARDINAL = new String[]{"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        //每上升三位之后的称呼
        String[] NUMS = new String[]{"", "Thousand", "Million", "Billion", "Trillion"};
        //存放每一块字符结果
        List<StringBuilder> parts = new ArrayList<>(10);
        int n = 0;
        while (num > 0) {
            //取出数字的后三位
            int tail = num % 1000;
            //转换这3位数字
            StringBuilder number = null;
            boolean finished = false;
            if (tail == 0) {
                //特殊情况，不用转换
                number = new StringBuilder();
            } else {
                StringBuilder sb = new StringBuilder();
                if (tail > 99) {
                    //超过99的需要转换百位，并将数字的百位去掉
                    int h = tail / 100;
                    sb.append(CARDINAL_NUMBER[h]).append(' ').append("Hundred");
                    tail = tail % 100;
                }
                if (tail > 0) {
                    //还有数字需要转换
                    if (sb.length() > 0) {
                        //说明转换过百位，需要添加空格以方便后面连接
                        sb.append(' ');
                    }
                } else if (sb.length() > 0) {
                    number = sb;
                    finished = true;
                }
                if (!finished) {
                    if (tail > 19) {
                        //大于19的数字需要做十位的转换
                        int t = tail / 10;
                        sb.append(TENS_CARDINAL[t]);
                        tail = tail % 10;
                        if (tail > 0) {
                            sb.append(' ').append(CARDINAL_NUMBER[tail]);
                        }
                    } else {
                        //19以内的数字直接取基数
                        sb.append(CARDINAL_NUMBER[tail]);
                    }
                    number = sb;
                }
            }
            if (n > 0 && number.length() > 0) {
                //n>0且存在转换结果时，连接千、百万、十亿的字样
                number.append(' ').append(NUMS[n]);
            }
            //n上升1
            ++n;
            if (number.length() > 0) {
                //存在转换结果，存放一块字符结果
                parts.add(number);
            }
            //整个数字往右移3位
            num = num / 1000;
        }
        //倒序方式拼接结果
        StringBuilder sb = parts.get(parts.size() - 1);
        for (int i = parts.size() - 2; i >= 0; --i) {
            sb.append(' ').append(parts.get(i));
        }
        if (sb.charAt(sb.length() - 1) == ' ') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }

    /**
     * 292【数学+贪心】Nim 游戏
     */
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }

    /**
     * 319【脑筋急转弯】灯泡开关
     * 经过动态规划模拟归纳可知，n可以由n-1的情况增加一个灯泡推导出来，增加的这一个灯泡又受到是否存在公约数而影响
     * 每存在一个公约数，则灯泡会被切换一次，灯泡从熄灭开始算，要变成亮的情况，需要操作奇数次
     * 因此当n存在奇数个公约数时，最后一个灯泡是亮的，会增加一个亮的灯泡
     * 而存在奇数个公约数的情况只有完全平方数可以，因此找到最近的完全平方数就是最近一个增加了亮的灯泡的情况
     */
    public int bulbSwitch(int n) {
        if (n < 4) {
            switch (n) {
                case 0: return 0;
                case 1:
                case 2:
                case 3:
                    return 1;
            }
        }
        for (int i = 2; i < 100000; ++i) {
            if (i * i > n) {
                return i - 1;
            }
        }
        return 100000;
    }

    /**
     * 326【数学】3的幂次
     */
    public boolean isPowerOfThree(int n) {
        //3的幂次可以为3^1、3^2、3^3......3^n，在int的最大值（2147483647）内最大的3的幂次为3^19 = 1162261467
        //由于3^19这个数的最小的质因子全是3，因此这个数一定能只能被3的幂次的数整除，因此这个小于等于这个数且能整除这个数的数一定是3的幂次
        return n > 0 && 1162261467 % n == 0;
    }

    /**
     * 330【数学】按要求补齐数组
     * O(n)
     * 0 ms
     * 一个很巧妙的方法，考虑从1开始合并出现的数的sum值，到不能覆盖到的数时+1取一个值就是patch，并且覆盖区域可以延伸到sum+patch
     */
    public int minPatches(int[] nums, int n) {
        int idx = 0, patchCount = 0;
        long sum = 0;
        while (sum < n) {
            if (idx > nums.length - 1 || sum < nums[idx] - 1) {
                long patch = sum + 1;
                ++patchCount;
                sum += patch;
            } else {
                sum += nums[idx];
                ++idx;
            }
        }
        return patchCount;
    }

    /**
     * 367【牛顿迭代法求平方根】完全平方数
     * https://www.cnblogs.com/qlky/p/7735145.html
     */
    public boolean isPerfectSquare(int num) {
        double n = num;
        double next = Math.abs(n + num / n) / 2;
        while (Math.abs(n - next) > 0.000001) {
            n = next;
            next = Math.abs(n + num / n) / 2;
        }
        int result = (int) n;
        return result * result == num;
    }

    /**
     * 375【博弈+动态规划+递归】猜数字大小 II
     * 思路：动态规划 + Minimax博弈思想
     * v_{i} = max_{a_{i}} min_{a_{-i}} {v_{i}(a_{i},a_{-i})}，https://en.wikipedia.org/wiki/Minimax
     * Minimax思想，指每次都考虑对手选了最优的步法（即自己每种选择的结果都最差min），最后在这些最差结果里面选择最优解max
     * 首先从博弈的角度考虑，每次选择都按最差的情况，我从1～n中随便挑一个数字，可以分成[1, i-1]、[i]、[i+1, n]三段
     * 考虑选数的人（对手）总是选你猜不透的数字，那么[i]就是猜不中的损失，于是我们要看看[1, i-1]和[i+1, n]的最差结果
     * 从中选出最差的作为我们必胜的至少消耗
     * 于是这里就引出动态规划了，[1, i-1]和[i+1, n]都是一些区间，我们把这些区间记录起来可以减少重复计算的次数
     * 考虑一些特殊情况，长度=1的区间不用损耗就可以得结果，损耗为0；长度=2的区间，只要猜损耗小的就可以得结果，损耗为较小的数
     */
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (i == j) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        recursion375(dp, 1, n);
        //这样针对[1,n]区间的必胜至少损耗就计算完成
        return dp[1][n];
    }
    /**
     * 递归计算一个区间[start, end]要猜出来至少要多少钱才能保证必胜，start和end都包含
     */
    private void recursion375(int[][] dp, int start, int end) {
        if (end - start == 1) {
            //长度=2，损耗为较小的数
            dp[start][end] = Math.min(start, end);
            return;
        }
        if (end - start < 1) {
            //长度=1，损耗为0
            dp[start][end] = 0;
            return;
        }
        for (int i = start; i <= end; ++i) {
            //对区间内的每一个位置都尝试猜一下并进行分割，分割后，需要记录左边子结果和右边子结果
            int leftLoss = 0, rightLoss = 0;
            if (i > start) {
                if (dp[start][i - 1] == Integer.MAX_VALUE) {
                    //能分割出左区间的情况，且左区间未计算，递归进行计算
                    recursion375(dp, start, i - 1);
                }
                //左区间的至少损耗
                leftLoss = dp[start][i - 1];
            }
            if (i < end) {
                if (dp[i + 1][end] == Integer.MAX_VALUE) {
                    //能分割出右区间的情况，且右区间未计算，递归进行计算
                    recursion375(dp, i + 1, end);
                }
                //右区间的至少损耗
                rightLoss = dp[i + 1][end];
            }
            //Minimax，先对左右区间的损耗进行比较，取max的（对于游戏者而言其实是min，该选法的最差结果），因为默认对手总是选你猜不透的数字
            //然后找到这些损耗中的最优解，取min（对于游戏者而言其实是max，最好的结果）
            dp[start][end] = Math.min(dp[start][end], Math.max(leftLoss + i, i + rightLoss));
        }
    }

    /**
     * 376【数学】摆动序列
     * 妙解，利用摆动序列，波峰和波谷的差值最多为1的特点。一次遍历，常数空间。
     * Angus-Liu
     */
    public int wiggleMaxLength(int[] nums) {
        //先讨论特殊情况
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        if (nums.length == 2) {
            if (nums[0] == nums[1]) {
                return 1;
            }
            return 2;
        }
        int up = 1;
        int down = 1;
        for (int i=1; i<nums.length; i++) {
            if (nums[i] > nums[i-1]) {
                up = down + 1;
            }
            if (nums[i] < nums[i-1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

    /**
     * 382【水塘抽样法】链表随机节点
     */
    static class Solution382 {
        ListNode head;
        Random random;
        public Solution382(ListNode head) {
            this.head = head;
            random = new Random();
        }
        public int getRandom() {
            int i = 1, ans = 0;
            for (ListNode node = head; node != null; node = node.next) {
                if (random.nextInt(i) == 0) { // 1/i 的概率选中（替换为答案）
                    ans = node.val;
                }
                ++i;
            }
            return ans;
        }
    }

    //p891
    private static final int MOD = 1000000007;
    /**
     * 由Tammon提供解题思路
     */
    public int p891SumSubseqWidths(int[] nums) {
        //由于只考虑子串，因此数字的顺序并不影响结果，所以可以排序，方便数学归纳分析
        Arrays.sort(nums);
        int n = nums.length;
        int[] factorial2 = new int[n];
        factorial2[0] = 1;
        for (int i = 1; i < n; ++i) {
            //计算出2的n次方的每个结果的结尾9位以内数字
            factorial2[i] = factorial2[i - 1] * 2 % MOD;
        }
        long result = 0;
        for (int i = 0; i < n; ++i) {
            //由数学归纳出每个数字作为最大值的贡献次数（2^i）和最小值的贡献次数（2^(n-i-1)），分别做乘法后相减得结果，注意防止溢出
            result = (result + ((long) factorial2[i] * nums[i]) % MOD - ((long) factorial2[n - 1 - i] * nums[i]) % MOD) % MOD;
        }
        return (int) result;
    }
    //p1017

    public String baseNeg2(int n) {
        if (n == 0) return "0";
        if (n == 1) return "1";
        int m = n;
        StringBuilder result = new StringBuilder();
        while (m != 0) {
            if ((m & 1) == 1) {
                result.insert(0, '1');
            } else {
                result.insert(0, '0');
            }
            m -= m & 1;
            m /= -2;
        }
        return result.toString();
    }

    //p1250
    public boolean isGoodArray(int[] nums) {
        int divisor = nums[0];
        for (int num : nums) {
            divisor = gcd(divisor, num);
            if (divisor == 1) {
                break;
            }
        }
        return divisor == 1;
    }

    private int gcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }

    //p1780
    public boolean checkPowersOfThree(int n) {
        if (n < 4) {
            //剩下1、2、3，其中2不能表示成3的n次幂
            return n != 2;
        }
        if (n % 3 == 0) {
            //整体剥离一个3，递归
            return checkPowersOfThree(n / 3);
        } else {
            //此时可以如果可以表示成3^0 + (3^i + ... + 3^j)，则去掉3^0再继续递归，否则就不能表示成3的幂和
            int next = n - 1;
            if (next % 3 == 0) {
                return checkPowersOfThree(next / 3);
            }
            return false;
        }
    }

    //p1823
    /**
     * 这还是一道约瑟夫环经典题。
     *
     * 每次往同一方向，以固定步长 kk 进行消数。由于下一次操作的发起点为消除位置的下一个点（即前后两次操作发起点在原序列下标中相差 kk），同时问题规模会从 nn 变为 n - 1n−1，因此原问题答案等价于 findTheWinner(n - 1, k) + k。
     * 以上解析来自于 https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/solution/by-ac_oier-qsuq/
     * 以n=5,k=2为例
     * 第一轮：移除2，下一轮从3开始,n=5，结尾为3，3即为结果
     * 1,2,3...1,2,3
     * 第二轮：n=4，结尾为1⬆
     *     1,2,3,...3,4,1
     * 第三轮：n=3，结尾为3⬆
     *         1,2,3,...1,2,3
     * 第四轮：n=2，结尾为1⬆
     *             1,2,1,2,1
     * 第五轮：n=1，结尾为1⬆
     *                 1
     *
     * 以n=6,k=5为例
     * 第一轮：移除5，下一轮从6开始,n=6，结尾为1，1即为结果
     * 1,2,3,4,5,6...2,3,4,5,6,1
     * 第二轮：n=5，结尾为2⬆
     *           1,2,3,4,5,1...2,3,4,5,1,2
     * 第三轮：n=4，结尾为2⬆
     *                   1,2,3,4,1,2...1,2,3,4,1,2
     * 第四轮：n=3，结尾为1⬆
     *                           1,2,3,1,2,3...2,3,1,2,3,1
     * 第五轮：n=2，结尾为2⬆，注意这一步result=1+5=6，6%2=0，题目要求从1到n，因此实际上result=2
     *                                   1,2,1,2,1,2,1,2,1,2
     * 第六轮：n=1，结尾为1⬆
     *                                           1
     */
    public int findTheWinner(int n, int k) {
        if (n == 1) {
            return 1;
        }
        int result =  findTheWinner(n - 1, k) + k;
        result = result % n;
        //题目要求从1到n，因此如果%n之后为0，代表应该在当次递归的第n个节点
        result = result == 0 ? n : result;
        return result;
    }

    //p1828
    public int[] countPoints(int[][] points, int[][] queries) {
        int[] answer = new int[queries.length];
        for (int j = 0; j < queries.length; ++j) {
            int cnt = 0;
            int[] query = queries[j];
            for (int[] point : points) {
                if (Math.abs(point[0] - query[0]) <= query[2] || Math.abs(point[1] - query[1]) <= query[2]) {
                    if ((point[0] - query[0]) * (point[0] - query[0]) + (point[1] - query[1]) * (point[1] - query[1]) <= query[2] * query[2]) {
                        //圆的数学公式，(x - a)^2 + (y - b)^2 = r^2
                        ++cnt;
                    }
                }
            }
            answer[j] = cnt;
        }
        return answer;
    }

    //p2427
    public int commonFactors(int a, int b) {
        int gcd = MathUtil.gcd(a, b);
        int cnt = 0;
        for (int i = 1; i <= gcd; ++i) {
            if (a % i == 0 && b % i == 0) {
                ++cnt;
            }
        }
        return cnt;
    }

    /**
     * 2562【数学+模拟】找出数组的串联值
     * 直接将两个数字转字符串、拼接、再转数字，最简单，但是速度慢O(n)
     * 更快的方式是先找出大于n2的一个10^n的数，n1直接乘以这个数再加上n2完成拼接，这样复杂度可以降到O(log(10)n)
     */
    public long findTheArrayConcVal(int[] nums) {
        long answer = 0L;
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            if (l == r) {
                answer += nums[l];
            } else {
                int n1 = nums[l];
                int n2 = nums[r];
                int p = 10;
                while (p <= n2) p *= 10;
                n1 = n1 * p + n2;
                answer += n1;
            }
            ++l;
            --r;
        }
        return answer;
    }

    public static void main(String[] args) {
        MathematicsSolution solution = new MathematicsSolution();
//        List<Integer> primes = solution.findPrimes(100001);
//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < primes.size(); ++i) {
//            sb.append(primes.get(i)).append(',');
//            if (i % 500 == 0) {
//                System.out.println(sb);
//                sb = new StringBuilder();
//            }
//        }
//        System.out.println(sb);
    }
}
